class Solution
{
public:
    int numSubarrayBoundedMax(vector<int> &nums, int left, int right)
    {
        int result = 0;
        int n = nums.size();
        vector<int> leftNextNonLess(n);
        vector<int> rightNextGreater(n);
        stack<int> s;
        for (int i = 0; i < n; ++i)
        {
            while (!s.empty())
            {
                if (nums[i] > nums[s.top()])
                {
                    s.pop();
                }
                else
                {
                    break;
                }
            }
            if (s.empty())
            {
                leftNextNonLess[i] = -1;
            }
            else
            {
                leftNextNonLess[i] = s.top();
            }
            s.push(i);
        }
        s = stack<int>();
        for (int i = n - 1; i >= 0; --i)
        {
            while (!s.empty())
            {
                if (nums[i] >= nums[s.top()])
                {
                    s.pop();
                }
                else
                {
                    break;
                }
            }
            if (s.empty())
            {
                rightNextGreater[i] = n;
            }
            else
            {
                rightNextGreater[i] = s.top();
            }
            s.push(i);
        }

        for (int i = 0; i < n; ++i)
        {
            if (nums[i] >= left && nums[i] <= right)
            {
                result += (i - leftNextNonLess[i]) * (rightNextGreater[i] - i);
            }
        }
        return result;
    }
};